package a00_LeetCode.Tree;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @Author quan
 * @Description 重要！！！必会！★♡☆★☆♡二叉树的层序遍历：借助队列
 * @Date 2023/3/24 21:17
 */
public class Num102_levelOrder {
    public List<List<Integer>> levelOrder(TreeNode root) {
        //注意：内层循环不能复用同一个数组
        //创建一个双层类型的集合用来保存最终结果：创建外层集合result保存的类型是集合
        List<List<Integer>> result = new ArrayList<>();
        if(root == null){
            return result;
        }
        //否则借助队列实现：先创建一个队列:队列里保存的是节点，所以是TreeNode类型
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offer(root);//添加根节点
        //当队列为空时，说明保存结束
        while (!deque.isEmpty()){
            int size = deque.size();
            //创建一个内层集合
            List<Integer> innerList = new ArrayList<>();
            for (int i = 0; i < size; i++) {//让当前节点的左右节点依次入栈
                TreeNode node = deque.poll();//让当前元素出栈
                if(node.left!=null){//让当前出栈的元素的左右节点依次入栈
                    deque.offer(node.left);
                }
                if(node.right!=null){
                    deque.offer(node.right);
                }
                //此时将出栈的节点保存在内层集合中：保存的类型是节点值
                innerList.add(node.val);
            }
            //将内层集合添加到外层集合中
            result.add(innerList);
        }
        return result;
    }
}
